//
// Created by SXL on 2025/8/17.
//

#include "simulate.hpp"
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <cmath>
using namespace  std;


//https://codefun2000.com/p/P3312 传感器数据分析
void simulateAnalized(){
    int cur = 0;
    pair<int,int> minans= {INT_MAX, INT_MAX};
    pair<int,int> maxans = {INT_MAX,INT_MIN};
    map<int, int> mp1,mp2;
    vector<int> ids(1010, 0);
    vector<int> times(1010, 0);
    int len= 0;
    while (cin >> ids[len] >> times[len]) {
        len++;
    }
    for(int i=0;i<len;i++){
        int delta = times[i]-cur;
        if(mp1.count(ids[i])){
            mp1[ids[i]]=max(delta,mp1[ids[i]]);

        }else{
            mp1[ids[i]]=delta;
        }
        cur = times[i];

    }
    cur =0;
    for(int i=0;i<len;i++){
        int delta = times[i]-cur;
        if(mp2.count(ids[i])){
            mp2[ids[i]]=min(delta,mp2[ids[i]]);
        }else{
            mp2[ids[i]]=delta;
        }
        cur = times[i];

    }
    for(auto p:mp1){
        if(p.second>maxans.second){
            maxans=p;
        }else if(p.second==maxans.second){
            if(p.first<maxans.first){
                maxans=p;
            }
        }


    }
    for( auto p:mp2){
        if(p.second<minans.second){
            minans=p;
        }else if(p.second==minans.second){
            if(p.first<minans.first){
                minans=p;
            }
        }


    }
    cout<<minans.first<<" "<<maxans.first;

}



//https://codefun2000.com/p/P2324 汇编作业
vector<int> a(32,0);
int toDigital(string s){
    return stoi(s.substr(1));
}
int getNum(string s){
    if(s[0]=='a'){
        return a[toDigital(s)];
    }else {
        return stoi(s);
    }

}

void compile()
{

    vector<string> cmds;
    string str;
    int len=0;
    while(getline(cin,str)){
        cmds.push_back(str);
        len++;
    }
    for(int i=0;i<len;i++){
        string cmd,re1,re2,re3;
        int idx=0;
        for( idx=0;idx<cmds[i].size();idx++){
            if(cmds[i][idx]!=' '){
                cmd+=cmds[i][idx];
            } else{
                break;
            }
        }
        idx++;
        for(;idx<cmds[i].size();idx++){
            if(cmds[i][idx]!=' '){
                re1+=cmds[i][idx];
            } else{
                break;
            }
        }
        idx++;
        for(;idx<cmds[i].size();idx++){
            if(cmds[i][idx]!=' '){
                re2+=cmds[i][idx];
            } else{
                break;
            }
        }
        idx++;
        for(;idx<cmds[i].size();idx++){
            if(cmds[i][idx]!=' '){
                re3+=cmds[i][idx];
            } else{
                break;
            }
        }

        if(cmd =="MOV"){
            a[toDigital(re1)] = getNum(re2);
        }else if(cmd =="ADD"){
            a[toDigital(re1)]= getNum(re2)+ getNum(re3);
        }else if(cmd == "SUB"){
            a[toDigital(re1)] =getNum(re2)- getNum(re3);
        }else if(cmd == "MUL"){
            a[toDigital(re1)] =getNum(re2)*getNum(re3);
        }else if(cmd == "DIV"){
            a[toDigital(re1)] =(int)floor((double)getNum(re2)/getNum(re3));
        } else if(cmd == "PRINT"){
            printf("%d\n",a[toDigital(re1)]);
        }

    }

}

//https://codefun2000.com/p/P2271 求一组算子的最短执行时间 暴力，其实可以双指针
void p2271(){
    int n=0;
    cin>>n;
    vector<int> nums(n+1);
    for(int i=1;i<=n;i++)
        cin>>nums[i];

    vector<int> sum(n+1,0);
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+nums[i];

    //结果
    int ans=sum[n];
    //记录当前ij的最大值
    int temp = sum[n];
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            int c = sum[j]-sum[i-1];
            int val =max(temp-c,c*6);
            ans =min(val,ans);
        }
    }
    cout<<ans;
}


//https://codefun2000.com/p/P2296  顺逆时针读取
void read_martix() {
    int n=0;
    cin>>n;
    vector<vector<int>> m(n,vector<int>(n,0));

    //    for(int i=0;i<n;i++){
    //        for(int j=0;j<n;j++){
    //            cin>>m[i][j];
    //        }
    //    }
    int left =0,right=n-1,top=0,bottom = n-1;
    int count=0;
    vector<int> ans;
    while(count<n*n){
        int i=left;

        for(;i<=right;i++){
            if(count>=n*n)break;
            cin>>m[top][i];
            count++;

        }
        top++;
        i=top;
        for(;i<=bottom;i++){
            if(count>=n*n)break;
            cin>>m[i][right];
            count++;
        }
        right--;
        i=right;
        for(;i>=left;i--){
            if(count>=n*n)break;
            cin>>m[bottom][i];
            count++;
        }
        bottom--;
        i=bottom;
        for(;i>=top;i--){
            if(count>=n*n)break;
            cin>>m[i][left];
            count++;
        }
        left++;
    }

    left =0,right=n-1,top=0,bottom = n-1;
    count=0;
    while(count<n*n){
        int i=top;
        for(;i<=bottom;i++){
            if(count>=n*n)break;
            ans.push_back(m[i][left]);
            count++;
        }
        left++;

        i=left;
        for(;i<=right;i++){
            if(count>=n*n)break;
            ans.push_back(m[bottom][i]);
            count++;
        }
        bottom--;

        i=bottom;
        for(;i>=top;i--){
            if(count>=n*n)break;
            ans.push_back(m[i][right]);
            count++;
        }
        right--;

        i=right;
        for(;i>=left;i--){
            if(count>=n*n)break;
            ans.push_back(m[top][i]) ;
            count++;
        }
        top++;
    }
    for(int i=0;i<ans.size();i++){
        if(i!=ans.size()-1){
            cout<<ans[i]<<" ";
        }else{
            cout<<ans[i];
        }
    }
}

//模拟 https://codefun2000.com/p/P3301 调试和对输入流的应用
//2
// algorithm 1-10,15-20
// algorithm 5-11
//1-11,15-20
bool compare(pair<int,int> a, pair<int,int> b) {
    if (a.first == b.first) {
        return a.second < b.second;
    }
    return a.first < b.first;
}
vector<pair<int,int> > parse(string &s) {
    vector<pair<int,int> > res;
    stringstream ss(s);
    string token;
    while (getline(ss, token, ',')) {
        int dash = token.find('-');
        if (dash == string::npos) {
            int x = stoi(token);
            res.push_back(make_pair(x, x));
        }
        else {
            int left = stoi(token.substr(0,dash));
            int right = stoi(token.substr(dash + 1));
            res.push_back(make_pair(left, right));
        }
    }
    return res;
}

vector<pair<int,int>> mergeInt(vector<pair<int,int> > v) {
    if (v.empty()) return v;
    sort(v.begin(), v.end(), compare);
    vector<pair<int,int> > res;
    auto [l,r] = v[0];
    for (int i=1;i<v.size();i++) {
        auto [l2,r2] = v[i];
        if (r + 1 < l2) {
            res.push_back(make_pair(l,r));
            l = l2;
            r = r2;
        }else {
            r=max(r,r2);
        }
    }
    res.push_back(make_pair(l,r));
    return res;
}
//删除操作
vector<pair<int,int> > subInt(vector<pair<int,int> > &v,vector<pair<int,int>> &del) {
    vector<pair<int,int> > cur=v;
    for (auto [dl,dr] : del) {
        vector<pair<int,int> > temp;
        for (auto[l,r] : cur) {
            if (r<dl||dr<l) {
                temp.push_back(make_pair(l,r));
            }else {
                if (l<dl) temp.push_back(make_pair(l,dl-1));
                if (r>dr) temp.push_back(make_pair(dr+1,r));
            }
        }
        cur=move(temp);
    }
    return mergeInt(cur);
}
void funcP3301() {
    int n=0;
    cin>> n;
    vector<pair<int,int> > db;
    string line;
    getline(cin,line);
    while (n--) {
        getline(cin,line);
        bool Undo = false;
        string data;
        if (line.find("undo",0)==0) {
            Undo = true;
            data = line.substr(line.find(' ',5)+1);
        }else {
            data = line.substr(line.find(' ')+1);

        }
        auto segs = parse(data);
        if (Undo) {
            if (!db.empty()) {
                db = subInt(db,segs);
            }
        }else {
            db.insert(db.end(),segs.begin(),segs.end());
            db =mergeInt(db);
        }
    }
    if (db.empty()) {
        cout<<0;
    }else {
        for (int i=0;i<db.size();i++) {
            auto[l,r]=db[i];
            if (l==r)cout<<r;
            else {
                cout<<l<<"-"<<r;
            }
            if (i+1<db.size()) {
                cout<<',';
            }
        }
    }

}

//  codefun2000.com/p/P2974 云计算服务器GPU分配  二进制枚举
void p2974() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long M;
    int N;
    long long R;
    cin>>M>>N>>R;

    vector<vector<tuple<int,int,int>>> segs(N);
    for (int i=0;i<N;i++) {
        int t;
        cin>>t;
        while (t--) {
            long long s,e,c;
            char ch;
            cin >> s >> ch >> e >> ch >> c;  // 读入格式 s:e:c
            segs[i].push_back(make_tuple(s,e,c));
        }
    }
    long long ans=0;
    for (int mask=0;mask<1<<N;mask++) {
        vector<long long > xs;
        long long w=0;
        for (int i=0;i<N;i++) {
            if (mask&(1<<i)) {
                for (auto &seg:segs[i]) {
                    long long s,e,c;
                    tie(s,e,c) = seg;
                    xs.push_back(s);
                    xs.push_back(e+1);
                    w+=(e-s+1)*c;
                }
            }
            if (xs.empty()) {
                continue;
            }
            sort(xs.begin(),xs.end());
            xs.erase(unique(xs.begin(),xs.end()),xs.end());
            vector<long long > diff(xs.size()+1);
            for (int i=0;i<N;i++) {
                if (mask&(1<<i)) {
                    for (auto &seg:segs[i]) {
                        long long s,e,c;
                        tie(s,e,c) = seg;
                        int l = lower_bound(xs.begin(), xs.end(), s) - xs.begin();
                        int r = lower_bound(xs.begin(), xs.end(), e+1) - xs.begin();
                        diff[l] += c;
                        diff[r] -= c;
                    }
                }
            }
            long long cur =0;
            bool ok = true;
            for (int i=0;i<xs.size();i++) {
                cur+=diff[i];
                if (cur>M) {
                    ok = false;
                }
            }
            if (ok) {
                ans=max(ans,w*R);
            }

        }
    }
    cout<<ans;
    return 0;
}

//https://codefun2000.com/p/P2959  救灾物资快速分配方案   无限制多行输入 最长连续子序列（滑动窗口）
//查找最长子序列
pair<int,int> find_max(vector<int> &arr,int val) {
    int l=0;
    int start=-1;
    ll sum =0;
    int maxlen =0 ;
    for(int r=0;r<arr.size();r++) {
        sum+=arr[r];
        while (l<=r&&sum>val) {
            sum-=arr[l];
            l++;
        }
        if (r-l+1>maxlen) {
            maxlen=r-l+1;
            start =l;
        }
    }
    return make_pair(start,maxlen);

}
void P2959() {
    vector<int> cars;
    vector<int> require;

    int x;
    //没有指定大小，就按行读入
    string line;
    if (!getline(cin,line)) {
        return 0;
    }
    istringstream ic(line);
    while (ic>>x) cars.push_back(x);

    getline(cin,line);
    istringstream ic2(line);
    while (ic2>>x) require.push_back(x);

    int m =cars.size();
    int n =require.size();
    int city =0;
    ll k  =cars[city];
    int ops=0;

    while (true) {

        auto [start,maxlen] = find_max(require,k);
        if (maxlen>0) {
            require.erase(require.begin()+start,require.begin()+start+maxlen);
            ops++;
            city++;
            if (city>=m) break;
            k=cars[city];
        }else {
            city++;
            if (city>=m)break;
            k+=cars[city];
        }
    }
    cout<<ops<<" "<<require.size();
    return 0;
}

//https://codefun2000.com/p/P2274   求最大括号表达式 字符串字典序最大、dfs compare
bool compare(const string &a,const string &b) {
    return a+b<b+a;
}
string dfs(string s) {
    if (s.empty()) {
        return "";
    }
    vector<string> part;
    string now;
    int cnt = 0;
    //分割括号
    for (char c:s) {
        if (c=='(') {
            cnt++;
        }
        else if (c==')') {
            cnt--;
        }
        now+=c;
        if (cnt==0) {
            part.push_back(now);
            now.clear();
        }
    }
    vector<string> subRes;
    if (part.size()==1) {
        //如果只有一个 则去掉最外层括号处理
        subRes.push_back("("+dfs(part[0].substr(1,part[0].size()-2))+")");
    }else {
        for (string p:part) {
            subRes.push_back(dfs(p));
        }
    }

    sort(subRes.begin(),subRes.end(),compare);
    string result ;
    for (const string &str:subRes) {
        result+=str;
    }
    return result;
}

//https://codefun2000.com/p/P2360 前缀和

void P2360() {
    int m;
    cin>>m;
    vector<vector<int>> grid(2,vector<int>(m,0));
    vector<vector<int>>  sum(2,vector<int>(m+1,0));

    for (int i=0;i<2;i++) {
        for (int j=0;j<m;j++) {
            cin>>grid[i][j];
        }
    }
    //sum[i]为下标从0~i-1的和
    for (int i=1;i<=m;i++) {
        sum[0][i]=sum[0][i-1]+grid[0][i-1];
        sum[1][i]=sum[1][i-1]+grid[1][i-1];
    }

    ll ans =LONG_LONG_MAX;

    for (int i=0;i<m;i++) {
        ll temp =max(sum[0][m]-sum[0][i+1],sum[1][i]);
        ans=min(temp,ans);

    }
    cout<<ans;
    return 0;
}

//https://codefun2000.com/p/P2362 循环数组 模拟就完事了 看懂题
void P2362() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    int target;
    cin >> target;

    // 1. 找到旋转点（数组从非递减变为递减的位置）
    int pivot = 0;
    for (int i = 1; i < n; i++) {
        if (arr[i] < arr[i-1]) {
            pivot = i;
            break;
        }
    }
    // 定义 start 和 end 用于记录目标值 t 的开始位置和结束位置
    int start = -1;
    int end = -1;

    // 遍历数组，按照旋转后的顺序查找目标值 t
    for (int i = 0; i < n; i++) {
        // idx 表示通过起点 s 重新计算的当前索引
        // (i + s) % n 用来模拟从起点开始循环的效果
        int idx = (i + pivot) % n;

        // 如果当前元素等于目标值 t
        if (arr[idx] == target) {
            // 如果是第一次找到目标值，记录其开始位置
            if (start == -1) {
                start = idx;
            }
            // 每次找到目标值时更新结束位置
            end = idx;
        }
    }

    // 输出目标值的开始位置和结束位置
    cout << start << " " << end << endl;
}

//https://codefun2000.com/record/68aeb89b7afad9053b999b04  哈希第一题
void hash1() {
    string line;
    getline(cin,line);
    stringstream ss(line);
    string n;
    map<int,int> m;
    int sum=0;
    while (getline(ss,n,',')) {
        int men = stoi(n);
        m[men]++;
        sum++;
    }
    vector<int> ans;
    for (auto p:m) {
        if (p.second>(sum)/2) {
            ans.push_back(p.first);
        }
    }
    if (ans.size()==0) {
        cout<<0;
    }else {
        for (auto i:ans) {
            cout<<i;
        }
    }

}

void hash2() {
    string s;
    getline(cin,s);
    stringstream ss(s);
    map<int,int> m;
    int sum=0;
    string n;
    vector<int> arr;
    while (getline(ss,n,',')) {
        int men = stoi(n);
        // m[men]++;
        // sum++;
        arr.push_back(men);
    }


    sort(arr.begin(),arr.end());
    pair<int,int > ans ={arr[0],1};
    pair<int,int> curr = {arr[0],1};
    int len=1;
    for (int i=1;i<arr.size();i++) {

        if (arr[i]==curr.first+curr.second) {
            curr.second++;
        }else {
            if (curr.second>ans.second) {
                ans.first = curr.first;
                ans.second = curr.second;
            }
            curr.first = arr[i];
            curr.second=1;
        }

    }
    if (curr.second>ans.second) {
        ans.first = curr.first;
        ans.second = curr.second;
    }

    // int ans=m.begin()->first;
    // for (auto p:m) {
    //     int i= p.first+1;
    //     while (m.find(i)!=m.end()) {
    //         m[p.first]++;
    //         i++;
    //     }
    //     if (m[ans]<m[p.first]) {
    //         ans=p.first;
    //     }
    // }
    cout<<ans.first<<","<<ans.second<<endl;
}

//https://codefun2000.com/p/P2247 hash 3
void hash3() {
    int n;
    cin>>n;
    vector<set<string>> arr;
    while (n--) {
        int m;
        cin>>m;
        set<string> temp;
        while (m--) {
            string s;
            cin>>s;
            temp.insert(s);
        }
        arr.push_back(temp);
    }


    for (int i=0;i<arr.size();i++) {
        int curmax=0;
        int index=0;
        for (int j=0;j<arr.size();j++) {
            if (i==j) continue;
            int sum=0;
            for (auto str:arr[i]) {
                if (arr[j].find(str)!=arr[j].end()) {
                    sum++;
                }
            }
            if (sum>curmax) {
                curmax = sum;
                index = j;
            }
        }
        cout<<index+1<<" "<<curmax<<endl;
    }
}


